// 通过数组算梯度
var maxProfit = function (prices) {
  let len = prices.length;
  let begin = 0;
  let end = 0;
  let sum = 0;
  for (let i = 1; i < len; i++) {
    if (prices[i] >= prices[end]) {
      end = i;
    } else {
      sum += prices[end] - prices[begin];
      begin = end = i;
    }
  }

  if (end !== begin) {
    sum += prices[end] - prices[begin];
  }

  return sum;
};

// 贪心解法
var maxProfit = function (prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1];
    }
  }
  return profit;
};

/* 
* 假设存在一段递增子数组 [a, b, c, d]，最大利润为 d - a。
* 而贪心算法会累加每一步的利润 (b-a) + (c-b) + (d-c) = d-a，结果相同
*/

let prices1 = [7, 1, 5, 3, 6, 4];
let prices2 = [1, 2, 3, 4, 5];
let prices3 = [6, 1, 3, 2, 4, 7];
console.log(maxProfit(prices2));
